#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
#include <map>

using namespace std;

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}

};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 

class Solution1 {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int p1 = 0, p2 = 0, n = pushed.size();
        while (p1 < n)
        {
            if (st.empty() || st.top() != popped[p2])
                st.push(pushed[p1]);
            while (!st.empty() && p2 < n && st.top() == popped[p2])
            {
                st.pop();
                ++p2;
            }
            ++p1;
        }
        return st.empty();
    }
};

class Solution2 {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return head;
        ListNode* s = head; ListNode* e = head->next;
        ListNode* list2 = e;

        while (e && e->next)
        {
            s->next = s->next->next; e->next = e->next->next;
            s = s->next; e = e->next;
        }
        s->next = list2;

        return head;
    }
};

class Solution3 {
public:
    using pci = pair<char, int>;

    class Less
    {
    public:
        bool operator()(pci p1, pci p2)
        {
            return p1.second < p2.second;
        }
    };

    string frequencySort(string s) {
        unordered_map<char, int> mp;
        for (char c : s) ++mp[c];
        priority_queue<pci, vector<pci>, Less> pq;
        for (auto& p : mp) pq.push(p);
        string res;
        while (!pq.empty())
        {
            pci p = pq.top();
            pq.pop();
            int cnt = p.second;
            while (cnt--)
                res.push_back(p.first);
        }
        return res;
    }
};

class Solution4 {
public:
    int maxOperations(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (int x : nums) {
            auto it = cnt.find(k - x);
            if (it != cnt.end() && it->second) {
                it->second--;
                ans++;
            }
            else {
                cnt[x]++;
            }
        }
        return ans;
    }
};

class Solution5 {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        for (int& t : time)
            t = t % 60;
        int res = 0;
        unordered_map<int, int> cnt;
        for (int t : time)
        {
            if (cnt.count((60 - t) % 60))
                res += cnt[(60 - t) % 60];
            ++cnt[t];
        }
        return res;
    }
};

class Solution6 {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        int next = targetSum - root->val;
        if (!root->left && !root->right) return !next;
        return hasPathSum(root->left, next) || hasPathSum(root->right, next);
    }
};